import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-21
 * Time: 9:48
 */


class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution5 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<List<Integer>> arrayList = new ArrayList<>();
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            while(true){
                TreeNode cur = queue.peek();
                if(queue.isEmpty()) break;
                queue.poll();
                list.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            arrayList.add(list);
        }
        return arrayList;
    }
}


class Solution2 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<List<Integer>> arrayList = new ArrayList<>();
        if(root==null) return arrayList;
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            int sz = queue.size();
            while(sz!=0){
                TreeNode cur = queue.poll();
                list.add(cur.val);
                sz--;
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            arrayList.add(list);
        }
        return arrayList;
    }
}


class Solution3 {
    public int maxDepth(TreeNode root) {
        //子问题思路就是找左子树和右子树的深度最大值+1就是整棵树的最大深度
        //1.确认递归的终止条件
        if(root==null) return 0;
        //计算左子树的高度
        int leftTree = maxDepth(root.left);
        //计算右子树的高度
        int rightTree = maxDepth(root.right);

        return leftTree>rightTree?leftTree+1:rightTree+1;
    }

    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        //左树的高度
        int leftH = maxDepth(root.left);
        //右树的高度
        int rightH = maxDepth(root.right);
        return (Math.abs(leftH-rightH)<=1)&&(isBalanced(root.left))
                &&(isBalanced(root.right));
    }
}


class Solution4 {
    public int maxDepth(TreeNode root) {
        //子问题思路就是找左子树和右子树的深度最大值+1就是整棵树的最大深度
        //1.确认递归的终止条件
        if(root==null) return 0;
        //计算左子树的高度
        int leftTree = maxDepth(root.left);
        //计算右子树的高度
        int rightTree = maxDepth(root.right);
        if(leftTree>=0&&rightTree>=0&&Math.abs(leftTree-rightTree)<=1){
            return Math.max(leftTree,rightTree)+1;
        }else {
            return -1;
        }
    }

    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        //左树的高度
        return maxDepth(root)>=0;
    }
}


class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {

        // Repeat the transform k times.
        for (;k > 0; k--) {

            int previous = grid[grid.length - 1][grid[0].length - 1];
            for (int row = 0; row < grid.length; row++) {
                for (int col = 0; col < grid[0].length; col++) {
                    int temp = grid[row][col];
                    grid[row][col] = previous;
                    previous = temp;
                }
            }
        }

        // Copy the grid into a list for returning.
        List<List<Integer>> result = new ArrayList<>();
        for (int[] row : grid) {
            List<Integer> listRow = new ArrayList<>();
            result.add(listRow);
            for (int v : row) listRow.add(v);
        }

        return result;
    }
}

//题目名称：
// 实现自己的 MyArrayList ，要求 implements java.util.List 接口
// 题目内容：
// 实现自己的 MyArrayList ，要求 implements java.util.List 接口

public class TestTemo {

    public static void main(String[] args) {
         Solution solution = new Solution();
         int[][] grid = {{1,2,3},{4,5,6},{7,8,9}};
         solution.shiftGrid(grid,1);
    }
}
